using System;
using System.Collections.Generic;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading;
namespace Leet
{
    class P1202
    {
        public static void Run()
        {
            var solution = new Solution();
            //Profiler.Run(solution.SmallestStringWithSwaps, "cba", CreatePairs(new (int, int)[] { (0, 1), (0, 2) }), ShowResult);
            //Profiler.Run(solution.SmallestStringWithSwaps, "cba", CreatePairs(new (int, int)[] { (0, 1), (0, 2) }), ShowResult);
            Profiler.Run(solution.SmallestStringWithSwaps, "dcab", CreatePairs("[0,3],[1,2]"), ShowResult);
            Profiler.Run(solution.SmallestStringWithSwaps, P1202Input.ReadV1(), CreatePairs(P1202Input.ReadV2()), ShowResult);
            Profiler.Run(solution.SmallestStringWithSwaps, "dcab", CreatePairs(new (int, int)[] { (0, 3), (1, 2), (0, 2) }), ShowResult);
            Profiler.Run(solution.SmallestStringWithSwaps, "dcab", CreatePairs(new (int, int)[] { (0, 3), (1, 2), (0, 2) }), ShowResult);
            Profiler.Run(solution.SmallestStringWithSwaps, "hezcdpnrbvdzgfxdascwldjdkcpuwnddnbklanxccrpmgkmbyztgeseoqzkmsurpjhxrdzphrnejbntfugilugftziomgdilmwlfaiqowuadfcdxutkkcmvsoscmvzoeezxhvrrsvibionettmierobtvefyozjbqbvzmygyevgbxeslcjsarbcmmsluxcjtjcjldjbeukudjqxzodfjuxscdjqwwfezglumpmvwkgdjhrugjvncpwghcmdttazkzaywetjzycwiericafayiomdsztdafvbzdzxkdeisruafcnqmvhnxgwzrvlrduvkcqatdiciiikxpofwabfkvwgsblsiavulwwbjffiubhvzmhqtlpjpbdckpabmkyppakerpuhlydeqxsolwudtklmunszjmdwcigkmacjehilxfxzsaqhhoaeczaltinrmmhyiidmmgixkhdidemrbsyigtdqdfayfjggpjeycpgnmkopdfexwfzanjdxbngcbsvyzesowohccswpwwptrjzwaakaxtozvttolzbxpodrwhuobdecgsrolwhyshhmnyhysbvkqrfhvyvlfogvdqloqvrslwnqbpugnqisccleprfhzpjmvxvuokdjkdfiqjgbflzxgwevxmczhzfposwedfjaphcpvaksunnzpnqwdffuvzdworggfykowtyfpjgmiqtgdofpydohmzctdhesqysrseznlnbqioftybxhdeccqwjbntpdhpbkueoutgfivpzvnlyfgsmnhgyqbwbrzamnnaixjvkvqkmcseqjmgvzhomxrwtrruorayttklwpoiabrfmhwgsvnjakdyxklrrpdmraiytsixhevxiuvwlxcavmmwucdeitkdepgihrlxozkutpnlzuhsjaqoqrqrgdidjyiguwjntqqudpnuxwqrgfmmlpapwzlzbeesvquzccemuclciybsytgwwwjujzfdvleoddgmukb",
            CreatePairs("[562,200],[605,394],[605,621],[376,615],[709,352],[418,347],[366,348],[12,912],[285,121],[107,357],[57,694],[122,802],[979,679],[188,142],[89,782],[541,720],[410,235],[269,707],[140,785],[558,69],[874,725],[494,685],[596,506],[432,819],[348,460],[818,384],[35,968],[194,913],[204,170],[171,329],[463,403],[846,865],[457,987],[384,802],[419,669],[499,138],[799,649],[295,118],[599,310],[308,205],[226,502],[990,739],[881,587],[847,671],[955,259],[128,814],[889,980],[531,775],[200,211],[349,301],[768,317],[491,407],[731,535],[418,426],[990,781],[203,110],[806,337],[976,969],[584,700],[438,979],[488,253],[439,335],[619,838],[502,657],[840,385],[342,704],[488,296],[235,112],[399,769],[342,454],[708,23],[864,559],[70,32],[74,660],[63,15],[416,262],[24,991],[260,874],[614,846],[461,951],[649,90],[757,911],[808,49],[420,804],[240,833],[424,809],[671,407],[79,411],[304,61],[894,136],[973,410],[935,590],[52,756],[200,558],[73,405],[89,648],[106,565],[821,89],[167,376],[163,229],[452,502],[364,431],[705,297],[346,981],[27,721],[483,566],[884,640],[248,29],[397,615],[435,703],[3,449],[287,290],[530,819],[59,946],[292,857],[772,596],[616,758],[994,759],[28,337],[471,289],[405,398],[461,173],[917,995],[954,901],[539,693],[847,994],[675,287],[384,916],[151,151],[35,68],[640,889],[126,435],[593,379],[605,751],[452,224],[71,963],[895,925],[776,510],[385,598],[926,633],[997,40],[123,56],[636,319],[758,548],[500,633],[849,532],[907,377],[900,84],[391,335],[82,835],[631,416],[747,926],[162,429],[230,714],[553,605],[24,762],[683,995],[332,682],[330,983],[379,959],[770,383],[688,978],[180,775],[914,478],[215,669],[965,482],[226,160],[76,451],[657,393],[565,181],[124,605],[343,824],[224,809],[636,452],[262,123],[872,903],[377,614],[94,186],[553,850],[442,253],[585,315],[661,684],[264,715],[352,835],[244,720],[135,905],[830,74],[218,447],[58,210],[907,350],[840,139],[420,133],[9,968],[656,497],[144,244],[101,261],[209,891],[889,487],[331,283],[771,187],[268,800],[549,962],[467,65],[890,923],[908,251],[904,532],[645,562],[678,766],[405,392],[410,856],[783,863],[485,498],[815,879],[714,358],[744,869],[463,664],[4,387],[489,494],[317,864],[322,112],[493,766],[984,276],[412,114],[920,868],[774,245],[812,486],[168,81],[745,62],[135,883],[447,919],[636,821],[672,614],[613,935],[466,496],[319,2],[326,420],[142,428],[87,73],[559,338],[86,837],[386,197],[2,381],[175,61],[392,440],[325,30],[191,548],[851,939],[353,454],[782,951],[248,954],[763,188],[918,586],[567,949],[154,447],[140,98],[928,830],[160,111],[803,700],[817,656],[866,139],[377,243],[770,486],[316,71],[681,990],[267,417],[960,888],[497,151],[654,489],[635,700],[261,134],[574,208],[860,63],[233,837],[783,38],[76,131],[718,828],[492,12],[105,604],[446,751],[409,398],[83,469],[374,658],[938,462],[750,841],[570,694],[70,860],[377,953],[578,657],[525,944],[583,576],[941,467],[968,484],[425,230],[747,483],[886,719],[499,417],[48,293],[765,325],[717,483],[894,967],[606,355],[976,931],[930,0],[659,938],[364,18],[488,378],[514,424],[485,36],[568,652],[367,386],[940,580],[451,29],[202,126],[148,160],[512,953],[489,915],[341,486],[281,456],[433,796],[89,220],[474,8],[18,88],[697,364],[545,57],[780,635],[321,585],[729,89],[316,467],[982,438],[166,122],[787,578],[392,846],[349,51],[116,212],[185,339],[307,985],[990,325],[860,318],[963,298],[346,93],[346,451],[206,895],[695,358],[527,690],[179,428],[615,943],[355,602],[774,127],[450,748],[297,369],[261,855],[124,955],[122,722],[320,812],[892,302],[83,523],[182,155],[644,127],[533,47],[613,741],[184,687],[277,108],[95,408],[787,991],[450,910],[569,499],[392,120],[500,736],[230,188],[50,213],[504,605],[408,418],[701,328],[945,679],[672,287],[959,52],[129,486],[790,622],[848,267],[377,577],[129,998],[796,966],[528,661],[312,501],[614,630],[713,827],[866,220],[408,205],[641,831],[901,141],[497,473],[433,580],[985,924],[598,185],[530,616],[440,415],[868,257],[50,383],[686,69],[452,30],[56,735],[534,543],[140,186],[421,311],[473,721],[783,929],[176,132],[15,170],[302,483],[236,673],[289,837],[746,130],[647,66],[575,371],[108,199],[80,885],[95,758],[538,191],[135,649],[361,298],[751,548],[688,697],[74,43],[364,663],[92,467],[733,49],[822,870],[246,438],[776,737],[4,349],[338,149],[354,179],[97,216],[757,884],[806,884],[31,133],[579,249],[591,694],[699,576],[457,853],[965,168],[425,843],[806,859],[927,66],[846,459],[957,282],[265,707],[217,37],[461,752],[834,155],[978,605],[993,503],[192,565],[934,906],[47,992],[432,498],[765,77],[243,301],[980,331],[394,343],[640,322],[708,504],[666,582],[966,655],[226,436],[538,449],[413,200],[226,28],[951,980],[754,906],[123,88],[354,869],[517,154],[182,140],[248,123],[160,64],[16,355],[469,239],[667,718],[451,967],[191,753],[351,701],[922,542],[902,493],[886,286],[428,504],[535,582],[14,69],[933,355],[677,294],[396,73],[339,125],[118,199],[333,375],[672,280],[620,531],[748,44],[126,324],[167,481],[809,733],[855,766],[502,7],[88,862],[804,518],[838,185],[554,544],[866,985],[673,560],[476,285],[554,571],[516,100],[686,497],[190,892],[115,101],[632,272],[350,87],[886,956],[212,985],[919,762],[82,592],[190,298],[928,255],[165,3],[553,964],[877,744],[181,29],[361,467],[273,871],[636,745],[990,263],[702,977],[576,511],[303,452],[112,663],[847,613],[403,983],[202,121],[918,484],[936,534],[762,821],[622,445],[733,219],[99,695],[117,121],[485,298],[701,837],[288,327],[345,661],[134,413],[988,894],[215,875],[480,761],[584,485],[130,752],[140,272],[318,562],[114,813],[806,899],[781,959],[268,775],[784,771],[203,998],[650,632],[99,850],[728,532],[958,19],[118,102],[476,106],[7,705],[987,331],[57,269],[305,861],[573,409],[719,317],[471,839],[948,542],[112,699],[534,950],[802,987],[659,312],[816,573],[585,465],[999,215],[101,695],[432,655],[305,798],[636,696],[186,284],[889,745],[599,963],[449,242],[236,754],[561,417],[633,250],[67,391],[862,282],[493,425],[398,552],[519,270],[680,234],[33,105],[459,815],[391,143],[179,195],[605,801],[329,554],[581,719],[766,692],[210,477],[877,778],[68,326],[577,189],[769,516],[483,190],[849,388],[940,317],[984,676],[861,51],[893,226],[394,642],[916,19],[214,464],[534,362],[841,210],[324,20],[419,853],[215,269],[516,401],[582,291],[878,124],[628,945],[564,93],[730,214],[763,839],[44,961],[844,266],[245,558],[584,832],[120,113],[38,745],[569,450],[221,729],[698,762],[360,443],[149,616],[343,914],[80,209],[526,435],[8,674],[454,839],[687,979],[122,170],[650,781],[495,822],[483,293],[327,411],[805,93],[672,285],[669,22],[644,160],[601,857],[514,886],[956,973],[246,480],[245,212],[80,809],[483,476],[140,351],[674,572],[807,373],[942,634],[456,449],[294,440],[541,998],[322,790],[833,615],[407,87],[736,496],[965,563],[685,730],[903,782],[39,587],[228,458],[284,129],[271,914],[11,555],[215,581],[808,632],[389,813],[518,762],[139,631],[172,129],[953,231],[235,381],[851,152],[553,97],[339,912],[694,540],[331,456],[456,1],[528,901],[27,525],[136,340],[347,593],[863,962],[172,805],[405,511],[209,113],[65,998],[974,47],[474,586],[219,54],[721,466],[40,790],[201,707],[505,770],[100,436],[832,782],[607,52],[500,664],[975,528],[169,659],[869,3],[997,693],[701,793],[74,20],[55,738],[620,845],[150,270],[255,623],[80,960],[302,256],[574,192],[941,190],[331,351],[747,670],[573,327],[607,914],[358,121],[135,621],[299,415],[553,557],[426,14],[15,805],[852,719],[184,132],[868,404],[816,754],[903,577],[848,753],[920,60],[513,781],[160,149],[839,935],[956,211],[431,695],[554,449],[192,385],[693,615],[34,55],[30,574],[321,940],[632,447],[225,674],[594,222],[732,568],[161,701],[645,688],[289,886],[565,570],[258,254],[245,162],[427,413],[374,980],[791,213],[841,811],[96,550],[311,726],[429,840],[928,616],[487,616],[41,219],[450,46],[166,191],[647,228],[666,909],[393,151],[355,733],[499,977],[405,997],[255,191],[290,126],[982,837],[342,632],[100,507],[372,720],[426,366],[560,515],[568,584],[526,785],[590,919],[930,798],[749,419],[687,699],[324,461],[739,610],[79,519],[395,415],[713,147],[67,370],[949,240],[324,353],[946,979],[828,28],[404,201],[950,817],[125,930],[325,23],[488,498],[352,592],[612,558],[201,106],[407,156],[350,368],[703,834],[580,939],[980,447],[298,540],[318,48],[180,26],[184,235],[477,745],[966,613],[121,797],[796,77],[564,914],[795,66],[636,115],[64,249],[755,474],[173,832],[673,521],[871,741],[937,22],[471,598],[555,300],[293,657],[819,26],[706,322],[468,919],[865,322],[741,440],[142,709],[812,979],[442,733],[220,470],[887,336],[545,403],[405,333],[471,295],[959,971],[638,899],[111,503],[249,384],[5,667],[435,158],[187,533],[379,722],[149,226],[48,469],[288,274],[224,381],[845,693],[464,828],[653,104],[802,183],[480,185],[359,576],[541,950],[804,533],[398,126],[487,806],[723,911],[396,9],[48,871],[413,638],[714,426],[171,518],[524,158],[735,682],[126,983],[742,650],[803,423],[352,516],[297,762],[946,794],[16,214],[114,226],[988,734],[809,719],[717,619],[325,878],[465,830],[436,773],[469,471],[694,685],[951,446],[181,647],[254,553],[400,446],[324,13],[769,138],[311,75],[983,731],[379,336],[493,613],[499,22],[646,279],[538,153],[362,882],[236,573],[371,237],[98,301],[568,710],[258,367],[203,526],[776,680],[269,19],[981,837],[710,775],[161,131],[112,249],[894,112],[941,671],[688,551],[308,891],[766,673],[26,726],[352,380],[404,636],[301,475],[91,375],[174,909],[176,758],[154,773],[919,796],[619,711],[450,56],[869,491],[155,849],[503,154],[700,454],[124,148],[322,742],[368,594],[780,706],[624,283],[687,115],[984,298],[527,414],[395,149],[936,139],[244,963],[639,148],[925,695],[547,209],[364,929],[771,10],[182,527],[849,156],[177,192],[886,44],[90,249],[797,501],[219,766],[753,199],[779,723],[604,814],[814,849],[461,58],[355,8],[804,792],[140,362],[620,933],[446,265],[823,485],[637,748],[343,607],[478,230],[650,143],[856,738],[86,376],[101,889],[551,42],[371,83],[481,877],[334,860],[895,135],[923,645],[842,617]"), ShowResult);
        }

        public static IList<IList<int>> CreatePairs((int, int)[] arr)
        {
            var allList = new List<IList<int>>();
            foreach (var tuple in arr)
            {
                allList.Add(new List<int>() { tuple.Item1, tuple.Item2 });
            }

            return allList;
        }

        public static IList<IList<int>> CreatePairs(string str)
        {
            var rg = new Regex(@"(\[[^\]]*\])");
            List<(int, int)> list = new List<(int, int)>();
            var collection = rg.Matches(str);
            foreach (Match match in collection)
            {
                var newStr = match.Value.Substring(1);
                newStr = newStr.Substring(0, newStr.Length - 1);
                var newTuple = newStr.Split(',');
                var v1 = int.Parse(newTuple[0]);
                var v2 = int.Parse(newTuple[1]);
                list.Add((v1, v2));
            }
            return CreatePairs(list.ToArray());
        }

        public static IList<IList<int>> CreatePairs(int[][] arr)
        {
            var allList = new List<IList<int>>();
            foreach (var tuple in arr)
            {
                allList.Add(new List<int>() { tuple[0], tuple[1] });
            }

            return allList;
        }


        public static void ShowResult(string result)
        {
            Console.WriteLine("result:" + result);
        }
        public class Solution
        {
            class DisjointSetUnion
            {
                public int[] rank, f;
                public int n;
                public DisjointSetUnion(int n)
                {
                    this.n = n;
                    rank = new int[n];
                    Array.Fill(rank, 1);
                    f = new int[n];
                    for (int i = 0; i < n; i++)
                    {
                        f[i] = i;
                    }
                }

                //返回父节点
                public int Find(int index)
                {
                    return f[index] == index ? index : Find(f[index]);
                }

                public void Set(int left, int right)
                {
                    left = Find(left);
                    right = Find(right);

                    if (left == right)
                        return;

                    //把节点数少的节点数多的上合并,因为少的找root比较快
                    //rank表示的是树中的节点数量,只有根节点的数据有效
                    if (rank[left] < rank[right])
                    {
                        var t = left;
                        left = right;
                        right = t;
                    }

                    rank[left] += rank[right];
                    f[right] = left;
                }
            }
            public string SmallestStringWithSwaps(string s, IList<IList<int>> pairs)
            {
                var arr = s.ToCharArray();
                //Profiler.Start("FillMap");
                DisjointSetUnion dis = new DisjointSetUnion(s.Length);
                foreach (var pair in pairs)
                {
                    var left = pair[0];
                    var right = pair[1];
                    if (left == right)
                        continue;
                    dis.Set(left, right);
                }
                //Profiler.End("FillMap");

                var groupMap = new Dictionary<int, List<char>>();

                for (int i = 0; i < arr.Length; i++)
                {
                    var root = dis.Find(i);
                    if (root == i && dis.rank[i] == 1)
                        continue;
                    if (!groupMap.ContainsKey(root))
                    {
                        groupMap[root] = new List<char>();
                    }
                    groupMap[root].Add(arr[i]);
                }

                foreach (var list in groupMap.Values)
                {
                    list.Sort((a, b) => -a.CompareTo(b));
                }

                var newArr = new char[arr.Length];
                //Profiler.Start("Change");
                for (int i = 0; i < arr.Length; i++)
                {
                    var root = dis.Find(i);
                    if (!groupMap.ContainsKey(root))
                    {
                        newArr[i] = arr[i];
                        continue;
                    }
                    var list = groupMap[root];
                    newArr[i] = list[list.Count - 1];
                    list.RemoveAt(list.Count - 1);
                }
                //Profiler.End("Change");

                return new string(newArr);
            }





        }
    }
}